/**
 * @program: LeetCode
 * @description: LeetCode :
 * @author: WXY
 * @create: 2023-01-03 16:24
 * @Version 1.0
 **/
public class Num134_canCompleteCircuit {
    public int canCompleteCircuit1(int[] gas, int[] cost) {
        for (int i = 0; i < cost.length; i++) {
            int rest = gas[i] - cost[i];
            int index = (i + 1) % cost.length;
            while (rest > 0 && index != i) {
                rest += gas[index] - cost[index];
                index = (index + 1) % cost.length;
            }
            if (rest >= 0 && index == i) return i;
        }
        return -1;
    }

    public int canCompleteCircuit2(int[] gas, int[] cost) {
        int curSum = 0;
        int min = Integer.MAX_VALUE;
        int len = gas.length;
        for (int i = 0; i < len; i++) {
            curSum += gas[i] - cost[i];
            if (curSum < min) {
                min = curSum;
            }
        }
        //从后往前，看谁能够填这个min
        if (curSum < 0) return -1;
        if (min >= 0) return 0;
        for (int i = len - 1; i >= 0; i--) {
            int res = gas[i] - cost[i];
            min += res;
            if (min >= 0) return i;
        }
        return -1;
    }

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curSum = 0;
        int totalSum = 0;
        int start = 0;
        int len = cost.length;
        for (int i = 0; i < len; i++) {
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if (curSum < 0) {
                start = i + 1;
                curSum = 0;
            }
        }
        if (totalSum < 0) return -1;
        return start;
    }

}
